
\chapter{Background}

\section{Chess Programs}

There is a very large number of programs allowing humans to play Chess on a computer. These are generally divided into \textit{Chess Engines} and \textit{Chess User Interfaces}. The player(s) interact with the interface, and the interface communicates with the engine, which is responsible for the rules of the game. This architecture is essentially a Model View Controller. Most chess software is written with `loose coupling' in mind, such that the engine and the interface need very little knowledge about one another to work together. They communicate by standardised protocols, for example \textit{Chess Engine Communication Protocol}, and can thus work equally well with any component supporting the protocol.

Should the player decide to play a computer (or set up a computer vs. computer game), the engine handles the AI.
\begin{comment}
Although \TC can be played on a standard Chess board (with pen and paper to keep track), it is not possible to make a \TC engine that is compatible with an existing Chess interface, because no existing Chess communication protocol has the capacity to transmit information about moves into the past or future. Any existing interface, engine or protocol would need to be modified to be used for \TC.
\end{comment}

\section{Current Chess AI}
Standard Chess is essentially beaten as an AI challenge. Easily available software running on a standard personal computer can beat master and even world champion human players. But some researchers find existing Chess AI unsatisfying, and Chess AI research has not provided as much that is useful outside of the field as was once expected. Successful Chess AIs do not think about Chess in the way that humans do. The algorithms used generally work by evaluating large numbers of potential moves, looking ahead several moves, and deciding on the best move based on those evaluations.

\begin{quote}
``
\textit{
\dots we should expect that machines will perform this narrow task so well \dots\xspace that their skill will be orders of magnitude superior to the best human play\dots
}

\textit{What will be the significance of this accomplishment for other areas of AI research? Sadly, not much. The brute force nature of the final solution might tell us how to go about building a parallel architecture `Go' or `Checker' machine, if we are so inclined, but it does not scale up to problems in robotics or expert systems, for example.}''

\raggedleft{\textit{-- L. Stephen Coles \cite{coles:2002:Online} }}
\end{quote}

We posit that if researchers are to make progress in Chess AI which will be useful in other fields, these brute-force based `successful but boring' approaches must first be broken. \TC aims to do that.

\section{Other \textit{HyperChesses}}
\label{other-hyperchesses}
\TC can be thought of as Chess extruded into the extra dimension of time. Chess games extruded into higher dimensions can be called \textit{HyperChesses}. Several HyperChesses have been designed \cite{pritchard2007classified}. Most of these extrude into a single higher spatial dimension, creating 3D Chess.

Perhaps the best known is ``{\fontspec{Trekbats}P} \textit{Tri-D Chess}'', which is played on a bizarre array of boards of different sizes. Programs like \textit{Parmen} allow this game to be played on a computer.

There is also Raumschach, a game played on a 5$\times$5$\times$5 board, and a large number of variants played on 8$\times$8$\times$3 boards, including Millennium 3d Chess and DragonChess.

Few attempts have been made to use Time as a dimension in HyperChess, and those that have have not been very serious. Jay Shaffstall proposed a `Temporal Chess' \cite{Shaffstall:Temporal}, but little came of it.

In all of these HyperChesses, with the possible exception of Raumshach, the extra dimension is treated as a `second-class citizen', either by the board being smaller in that dimension, or by having movement in that dimension occur under limited or varied rules. In \TC, we aim to have $t$ be as important a coordinate as $x$ or $y$.

\section{Other Complex Games}

There are many games designed to be complex, and some that are specifically designed to be challenging for machine players.

\subsection{Go}

Go is a highly complex game \cite{allis1994searching}, and provides a much more difficult challenge in AI research than Chess. The reasons for this are explored in detail in \citeasnoun{crasmaru1999complexity}, we will only briefly summarise them here.

\begin{itemize}
\item The board is 19$\times$19, much larger than a chess board.

\item Movement is less restricted. Generally almost any unoccupied space is a legal move.

\item The game becomes more complex as it goes on, as pieces are added, in contrast to Chess, in which pieces are removed.

\item Evaluating a move requires analysis of the structure of the layout, with few of the computationally cheap move evaluation factors available to Chess, like ``What's the value of the pieces I can take if I make this move''.
\end{itemize}

For these reasons, Go is thought of by many as the next challenge and focus of game AI research \cite{stonebrief}. However, there are also those who think that Chess still has a lot to teach us \cite{iqbalcomputer}, and should not be abandoned yet.

\subsection{Arimaa}

Arimaa is a game designed with fairly similar goals to those of \TC. It is intended to be playable by a four year old, and very difficult to play for an AI \cite{syed2003arimaa}. One way in which it poses a problem for brute-force based AI players is by having a very high number of possible moves available each turn ($\sim$17,281 compared to Chess' $\sim$35). The number (called the \textit{branching factor}) is so high in Arimaa because each turn is made up of several moves, and there are several choices that need to be made in each move. In chess, there is only one move per turn, and two choices to be made per move - which piece to move, and where to move it to. There are a maximum of 16 pieces from which to choose, and generally only a few possible moves for a piece. For example, Knights get at most 8 possible moves, and the most mobile piece, a queen, when placed in its most free position, the centre of the board, still has only 27 possible moves.

In Arimaa, four moves a turn are possible, immediately increasing possibilities by a factor of four. However, not all four moves must be used each turn, a player can elect to make any number of moves between one and four. This further increases the number of possible turns. The player may elect to allocate their up to four moves however they want between their pieces, further increasing the number of possibilities. The game revolves around a mechanic of `pushing and pulling', by which pieces can move opposing pieces on the board. A piece can move away from an opposing piece leaving it in place, or it can move and pull the opposing piece with it, which provides another choice, doubling the search space for many moves. Each extra choice provides an extra dimension to the abstract turn-space, exponentially increasing the size of that space (this is often called ``The Curse of Dimensionality''). The resulting explosion of options makes the search space extremely large and difficult for an AI to handle, but doesn't inconvenience human players much.

Human players can be thought of as having a particular maneuver, goal or strategy in mind, and searching for a way to work within the restrictions set by the game rules to achieve that aim.

Most Chess AIs can be thought of as having a space of possible moves, and attempting to search that space for a good move to play.

Looked at in this way it is clear that for a human, more freedom means weaker restrictions applied by the game, which makes it easier to play, but for a Chess AI that freedom means a much larger move-space to search. More choice makes things easier for the human and harder for the AI.

\subsubsection{Difference to \TC}

The aims of Arimaa vary from those of \TC, in that Arimaa attempts to be simple for a human and difficult for a machine, whilst \TC makes no attempt to be simple for a human to play.

While Arimaa, like \TC, can be played on a standard chessboard, Arimaa is so radically different in its gameplay that it cannot be considered a `chess variant', but is rather a completely different game played on the same board. Advances in Arimaa AI may not be helpful in developing more interesting AI for normal Chess. \TC on the other hand is similar enough to Chess that advances in \TC AI are more likely to be applicable to standard Chess.

